class BinarySearch:
    """
    Binary Search class that contains various implementations of the binary search algorithm.
    """

    def binary_search(self, arr, target):
        """
        Standard binary search method implemented using an iterative approach.

        Args:
        - arr: Sorted list
        - target: Target element to search for

        Returns:
        - If the target element is found, returns its index
        - If the target element is not found, returns -1
        """
        low, high = 0, len(arr) - 1

        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return -1

    def binary_search_recursive(self, arr, target, low, high):
        """
        Recursive binary search method.

        Args:
        - arr: Sorted list
        - target: Target element to search for
        - low: Starting index of the search range
        - high: Ending index of the search range

        Returns:
        - If the target element is found, returns its index
        - If the target element is not found, returns -1
        """
        if low > high:
            return -1

        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return self.binary_search_recursive(arr, target, mid + 1, high)
        else:
            return self.binary_search_recursive(arr, target, low, mid - 1)

    def binary_search_approximate(self, arr, target):
        """
        Approximate binary search method to find the closest element to the target.

        Args:
        - arr: Sorted list
        - target: Target element to search for

        Returns:
        - If the target element is found, returns its index
        - If the target element is not found, returns the element closest to the target
        """
        low, high = 0, len(arr) - 1
        closest = None

        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

            if closest is None or abs(arr[mid] - target) < abs(closest - target):
                closest = arr[mid]

        return closest

    def binary_search_first_occurrence(self, arr, target):
        """
        Binary search method to find the index of the first occurrence of the target element.

        Args:
        - arr: Sorted list
        - target: Target element to search for

        Returns:
        - If the target element is found, returns the index of its first occurrence
        - If the target element is not found, returns -1
        """
        low, high = 0, len(arr) - 1
        result = -1

        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == target:
                result = mid
                high = mid - 1
            elif arr[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return result

    def binary_search_last_occurrence(self, arr, target):
        """
        Binary search method to find the index of the last occurrence of the target element.

        Args:
        - arr: Sorted list
        - target: Target element to search for

        Returns:
        - If the target element is found, returns the index of its last occurrence
        - If the target element is not found, returns -1
        """
        low, high = 0, len(arr) - 1
        result = -1

        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == target:
                result = mid
                low = mid + 1
            elif arr[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return result

    def binary_search_first_greater(self, arr, target):
        """
        Binary search method to find the index of the first element greater than the target.

        Args:
        - arr: Sorted list
        - target: Target element to search for

        Returns:
        - If an element greater than the target exists, returns the index of the first occurrence
        - If no element greater than the target exists, returns -1
        """
        low, high = 0, len(arr) - 1
        result = -1

        while low <= high:
            mid = (low + high) // 2
            if arr[mid] > target:
                result = mid
                high = mid - 1
            else:
                low = mid + 1

        return result

    def binary_search_last_smaller(self, arr, target):
        """
        Binary search method to find the index of the last element smaller than the target.

        Args:
        - arr: Sorted list
        - target: Target element to search for

        Returns:
        - If an element smaller than the target exists, returns the index of the last occurrence
        - If no element smaller than the target exists, returns -1
        """
        low, high = 0, len(arr) - 1
        result = -1

        while low <= high:
            mid = (low + high) // 2
            if arr[mid] < target:
                result = mid
                low = mid + 1
            else:
                high = mid - 1

        return result


# Usage example
if __name__ == "__main__":
    my_list = [1, 2, 4, 5, 7, 9]
    target_element = 5

    binary_search_obj = BinarySearch()

    # Standard binary search
    result = binary_search_obj.binary_search(my_list, target_element)
    # Output: Standard binary search result: 3
    print("Standard binary search result:", result)

    # Recursive binary search
    result = binary_search_obj.binary_search_recursive(my_list, target_element, 0, len(my_list) - 1)
    # Output: Recursive binary search result: 3
    print("Recursive binary search result:", result)

    # Approximate binary search
    result = binary_search_obj.binary_search_approximate(my_list, target_element)
    # Output: Approximate binary search result: 5
    print("Approximate binary search result:", result)

    # Binary search for first occurrence
    result = binary_search_obj.binary_search_first_occurrence(my_list, target_element)
    # Output: Index of the first occurrence: 3
    print("Index of the first occurrence:", result)

    # Binary search for last occurrence
    result = binary_search_obj.binary_search_last_occurrence(my_list, target_element)
    # Output: Index of the last occurrence: 3
    print("Index of the last occurrence:", result)

    # Binary search for first element greater than the target
    result = binary_search_obj.binary_search_first_greater(my_list, target_element)
    # Output: Index of the first element greater than the target: 4
    print("Index of the first element greater than the target:", result)

    # Binary search for last element smaller than the target
    result = binary_search_obj.binary_search_last_smaller(my_list, target_element)
    # Output: Index of the last element smaller than the target: 2
    print("Index of the last element smaller than the target:", result)
